﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0147_Divide : IAlgorithm
    {
        // 两数相除

        // 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
        // 返回被除数 dividend 除以除数 divisor 得到的商。
        // 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

        // 提示：
        //  被除数和除数均为 32 位有符号整数。
        //  除数不为 0。
        //  假设我们的环境只能存储 32 位有符号整数，其数值范围是[−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

        public void Test()
        {
            Console.WriteLine(Divide(7, -3));
        }

        // 算法 dividend divisor
        public int Divide(int dividend, int divisor)
        {
            if (divisor == 1) return dividend;
            if (divisor == -1) return (dividend == int.MinValue) ? int.MaxValue : -1 * dividend;
            if (divisor == int.MinValue) return (dividend == int.MinValue) ? 1 : 0;

            bool flag = ((dividend ^ divisor) & 0x80000000) != 0;
            int c = 0;
            // convert to minus and calc
            if (divisor > 0) divisor = -1 * divisor;
            if (dividend > 0) dividend = -1 * dividend;
            while (dividend <= divisor)
            {
                int x = -divisor;
                int c1 = 1;
                while ((x << 1) > 0 && -1 * (x << 1) > dividend)
                {
                    c1 += c1;
                    x <<= 1;
                }
                c += c1;
                dividend += x;
            }
            return flag ? -1 * c : c;
        }
    }
}
